Support Vector Machines

class: center, middle, inverse, title-slide

# Support Vector Machines
## 🚧 🛣️ 🦿
### Applied Machine Learning in R Pittsburgh Summer Methodology Series
### Lecture 4-A     July 22, 2021

---

class: inverse, center, middle
# Overview

---
class: onecol
## Roadmap

1. Maximal Margin Classifier 🚶

1. Support Vector Classifier 🏃

1. Support Vector Machine 🚴

1. Applied Example

1. Support Vector Regression

1. Live Coding

1. Hands-on Activity

---
class: onecol
## Notices and Disclaimers

The ideas underlying SVM are really *clever* and *interesting*! 😃

SVM is also a good algorithm for *smaller*, *messy* datasets!! 😍

However, there is a lot of *terminology* and *math* involved... 😱

I will try to shield you from this and give only the necessities

- That means there will be some things I need to "hand waive"

- I may also need to skip questions with very technical answers

But you should get a strong intuition and applied knowledge

- This will prepare you nicely to dive into a longer course on the topic

---
class: inverse, center, middle
# SVM Intuitions
---
class: onecol
## A Tale of Two Classes

If this is our training data, how do we **predict the class** of new data?

---
class: onecol
## Drawing a Line in the Sand

With one feature, we could find a **point** that separates the classes (as higher or lower)

---
class: onecol
## Analysis Paralysis
But there are many possible decision points, so **which should we use?**

---
class: onecol
## Maximal Margin Classifier (MMC)
The MMC algorithm finds and uses the point with the **largest** (i.e., maximal) ![:emphasize](margin)

---
class: onecol
## Maximal Margin Classifier

If we have two features, we can extend this idea using a 2D plot and a decision **line**

---
class: onecol
## Maximal Margin Classifier

If we have three features, we will need a 3D plot and a decision **plane** (i.e., flat surface)

.footnote[[1] Credit to [Zahra Elhamraoui](https://medium.datadriveninvestor.com/support-vector-machine-svm-algorithm-in-a-fun-easy-way-fc23a008c22) for this visualization.]

---
class: onecol
## Maximal Margin Classifier

If we have four or more features, we will need a decision **hyperplane**

.bg-light-yellow.b--light-red.ba.bw1.br3.pl4[
**Caution:** You may hurt yourself if you try to imagine what a hyperplane looks like. 
.tr.pr4[
But here is a hint: 🍫✈️
]
]

.pt1[
**Margins still exist** in higher-dimensional space and we still want to maximize them
]

- Our goal is thus to locate the class-separating hyperplane with the largest margin

- The math behind this is beyond the scope of our workshop, but that's the idea

.pt1[
We can still **classify new observations**: which side of the hyperplane do they fall on?
]

---
class: onecol
## Maximal Margin Classifier

Only the observations that define the margin, called ![:emphasize](support vectors), are used

Because it only uses a subset of data anyway, MMC does well with smaller datasets

---
class: onecol
## Maximal Margin Classifier

This means that **outliers can have an outsized impact** on what is learned

For instance, this margin is likely to misclassify examples in new data

---
class: onecol
## Support Vector Classifier (SVC)

The SVC algorithm is like MMC but it **allows examples to be misclassified** (i.e., wrong)

This will **increase bias** (training errors) but hopefully **decrease variance** (testing errors)

---
class: onecol
## Support Vector Classifier

SVCs also enable a model to be trained when the classes are **not perfectly separable**

A straight line is never going to separate these classes without errors (sorry MMC...)

---
class: onecol
## Support Vector Classifier

But if we allow a few errors and points within the margin...

...we may be able to find a hyperplane that generalizes pretty well

---
class: onecol
## Support Vector Classifier

When points are on the wrong side of the margin, they are called "violations"

A **softer margin** allows more violations, whereas a **harder margin** allows fewer

SVCs have a hyperparameter `$C$` that controls how soft vs. hard the margin is

- A **lower `$C$` value** makes the margin harder (allows fewer violations)1
 
 As a result, the model has **lower bias** and more flexibility but may overfit

- A **higher `$C$` value** makes the margin softer (allows more violations)

As a result, the model has less flexibility but may also have **lower variance**

.footnote[[1] If you set `\$C=0\$` (i.e., a fully hard margin) SVC will allow no violations  and behave the same as MMC.]

---
class: onecol
## Support Vector Machine

So far, MMC and SVCs have both used linear (e.g., flat) hyperplanes

But there are many times when the classes are not **linearly separable**

.footnote[[1] Good luck separating these classes with a single decision point...]

---
class: onecol
## Support Vector Machine

But if we enlarge the feature space, the classes might then become linearly separable

There are many ways to do this enlarging, but one is to add polynomial expansions

---
class: onecol
## Support Vector Machine

The classes are now linearly separable in this new enlarged feature space!

---
class: onecol
## Support Vector Machine

Here is a more complex example of a nonliner (and non polynomial) expansion

.footnote[[1] Credit to [Erik Kim](https://www.eric-kim.net/eric-kim-net/posts/1/kernel_trick.html) for this example and visualization.]

---
class: onecol
## Support Vector Machine

And here is the hyperplane (linear in 3D but nonlinear when "projected" back in 2D)

.footnote[[1] Credit to [Erik Kim](https://www.eric-kim.net/eric-kim-net/posts/1/kernel_trick.html) for this example and visualization.]

---
class: onecol
## Support Vector Machine
The ![:emphasize](Support Vector Machine) (SVM) allows us to efficiently enlarge the feature space

- Part of what makes SVMs efficient is they **only consider the support vectors**

- They also use **kernel functions** to quantify the similarity of pairs of support vectors1

.footnote[[1] These similarity estimates are used to efficiently find the optimal hyperplane but that process is complex.]

The SVC can actually be considered a simple version of the SVM with a linear kernel

- A linear kernel essentially quantifies similarity using the Pearson correlation

`$$k(x, x') = \langle x, x'\rangle$$`

Linear kernels are efficient but nonlinear kernels may provide better performance

---
exclude: true
class: onecol
## Support Vector Machine

It is common to also use **nonlinear** kernels, such as the ![:emphasize](polynomial kernel)

`$$k(x, x')=(\text{scale} \cdot \langle x, x' \rangle + \text{offset})^\text{degree}$$`

With larger values of `$\text{degree}$`, the decision boundary can become more complex

- You are essentially adding polynomial expansions of `$\text{degree}$` to each predictor

- You have expanded the feature space and may now have linear separation

- This is the same idea we just used in fitting a hyperplane in the `$x\text{-by-}x^2$` space!

If you center or normalize all your predictors, you can drop the `$\text{offset}$` term

.footnote[[1] When `\$\text{degree}=1\$`, the polynomial kernel reduces to the linear kernel and SVM becomes SVC again.]

---
class: onecol
## Support Vector Machine

Perhaps the most common nonlinear kernel is the ![:emphasize](radial basis function) (RBF)

`$$k(x, x') = \exp\left(-\sigma \|x-y\|^2\right)$$`

The intuition here is that similarity is weighted by how *close* the observations are

- Only support vectors near new observations influence classification strongly

- As the `$\sigma$` hyperparameter1 increases, the more *local* and complex fit becomes

The RBF kernel computes similarity between points in *infinite* dimensions 🤯

- It is considered an ideal "general purpose" nonlinear kernel2

.footnote[
[1] Note that `$\sigma$` is also sometimes called `$\gamma$` or the "scale" hyperparameter. 
[2] Other nonlinear kernels are popular for special purposes and in specialized subfields.
]

---
## Support vector regression

---
## Applied Example

---
## Live Coding Activity

---
## Hands-on Activity

---
## Break and timer